"""
56. 携带矿石资源（第八期模拟笔试）
https://kamacoder.com/problempage.php?pid=1066
题目描述
你是一名宇航员，即将前往一个遥远的行星。在这个行星上，有许多不同类型的矿石资源，每种矿石都有不同的重要性和价值。
你需要选择哪些矿石带回地球，但你的宇航舱有一定的容量限制。 
给定一个宇航舱，最大容量为 C。现在有 N 种不同类型的矿石，每种矿石有一个重量 w[i]，一个价值 v[i]，以及最多 k[i] 个可用。
不同类型的矿石在地球上的市场价值不同。你需要计算如何在不超过宇航舱容量的情况下，最大化你所能获取的总价值。

输入描述
```
输入共包括四行，第一行包含两个整数 C 和 N，分别表示宇航舱的容量和矿石的种类数量。 
接下来的三行，每行包含 N 个正整数。具体如下： 
第二行包含 N 个整数，表示 N 种矿石的重量。 
第三行包含 N 个整数，表示 N 种矿石的价格。 
第四行包含 N 个整数，表示 N 种矿石的可用数量上限。
```

输出描述
输出一个整数，代表获取的最大价值。
输入示例
10 3
1 3 4
15 20 30
2 3 2
输出示例
90

提示信息
数据范围：
1 <= C <= 2000;
1 <= N <= 100;
1 <= w[i], v[i], k[i] <= 1000;
"""
from typing import List
import math


class Solution:
    """
    多重背包问题最简单的思路就是把物品数量平铺，即有m种物品，每种物品有k个，那么就平铺成m*k个物品，然后求解01背包问题。
    但是这样复杂度挺高，可能会超时。
    
    """
    def mining(self, n: int, weights:List, nums:List, values:List) -> int:
        # 定义dp数组
        dp = [0] * (n+1)
        # 初始化
        dp[0] = 0
        # 物品等价于 weights * nums
        for i, _ in enumerate(weights):
            for j in range(nums[i]):
                # 遍历背包 一维dp需要逆序遍历!!!!!!!!
                for k in range(n, 0, -1):
                    if k >= weights[i]:
                        dp[k] = max(dp[k], dp[k-weights[i]] + values[i])
                    else:
                        dp[k] = dp[k]
        return dp[-1]
    
    # 标准解法
    def mining(self, n, weights:List, nums:List, values:List):
        
        dp = [0] * (n + 1)
        # 遍历物品种类
        for i in range(len(weights)):
            # 遍历背包容量
            for j in range(n, weights[i] - 1, -1):
                # 遍历物品个数，将k个物品依次放入背包，判断放入几个可以取最大值
                for k in range(1, nums[i] + 1):
                    # 如果已经大于背包容量直接跳出循环
                    if k * weights[i] > j:
                        break
                    dp[j] = max(dp[j], dp[j - weights[i] * k] + values[i] * k) 
        
        return dp[-1]


if __name__ == "__main__":
    so = Solution()
    c, n = map(int, input().split())
    weights = [int(i) for i in input().split()]
    values = [int(i) for i in input().split() if i]
    nums = [int(i) for i in input().split()]
    n = so.mining(c, weights, nums, values)
    print(n)